//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1']
//,['1','0','0','1','0']]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：matrix = [['0','1'],['1','0']]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：matrix = [['0']]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 300 
// matrix[i][j] 为 '0' 或 '1' 
// 
// Related Topics 动态规划 
// 👍 641 👎 0

package com.leetcode.editor.cn;

//Java：最大正方形
class P221MaximalSquare {
    public static void main(String[] args) {
        Solution solution = new P221MaximalSquare().new Solution();
        // TO TEST
//        char[][] matrix = {{'1', '0', '1', '0'}, {'1', '0', '1', '1'}, {'1', '0', '1', '1'}, {'1', '1', '1', '1'}};
//        char[][] matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
//        char[][] matrix = {{'1', '1', '1', '1', '0'}, {'1', '1', '1', '1', '0'}, {'1', '1', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'0', '0', '1', '1', '1'}};
//        char[][] matrix = {{'1'}};
        char[][] matrix = {{'1', '1', '1', '1', '1', '1', '1', '1'}
                , {'1', '1', '1', '1', '1', '1', '1', '0'}
                , {'1', '1', '1', '1', '1', '1', '1', '0'}
                , {'1', '1', '1', '1', '1', '0', '0', '0'}
                , {'0', '1', '1', '1', '1', '0', '0', '0'}};
        int square = solution.maximalSquare(matrix);
        System.out.println(square);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalSquare(char[][] matrix) {
                int maxSide = 0;
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            int m = matrix.length;
            int n = matrix[0].length;
            //1.暴力解法
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (matrix[i][j] == '1') {
//                        //以此为顶点，向右下方搜索
//                        int side = search(matrix, i, j);
//                        maxSide = Math.max(side, maxSide);
//                    }
//                }
//            }
            //2.动态规划
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(matrix[i][j]=='1'){
                        if(i==0||j==0){
                            dp[i][j] = 1;
                        }else{
                            dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        }
                        maxSide = Math.max(maxSide, dp[i][j]);
                    }
                }
            }
            return maxSide * maxSide;
        }

        private int search(char[][] matrix, int row, int col) {
            int loop = 1;
            int rows = matrix.length;
            int cols = matrix[0].length;
            matrix[row][col] = '0';
            while (row + loop < rows && col + loop < cols) {
                boolean flag = true;
                for (int i = 0; i <= loop; ++i) {
                    if (matrix[row + loop][col + i] == '0') {
                        flag = false;
                        break;
                    }
                    if (matrix[row + i][col + loop] == '0') {
                        flag = false;
                        break;
                    }
                }
                if (!flag) break;
                loop++;
            }
            return loop;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}